{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "6cb0fb42-4770-4678-958f-eb8876d427a1",
   "metadata": {},
   "source": [
    "# Evaluate Summarization"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e5bd4904-9cf4-4e3c-89c5-5c5fed28455b",
   "metadata": {},
   "source": [
    "| | |\n",
    "|----------|-------------|\n",
    "| Author(s)   | Renato Leite (renatoleite@), Egon Soares (egon@) |\n",
    "| Last updated | 09/05/2023 |"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "95d439eb-277b-4721-aa59-83cbdb14cf75",
   "metadata": {},
   "source": [
    "## ROUGE-L"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a02536af-c4f5-4e18-ae24-fe8e84bd4300",
   "metadata": {},
   "source": [
    "ROUGE-L uses LCS-based F-measure to estimate the similarity between two summaries X of length m and Y of length n, assuming X is a reference summary sentence and Y is a candidate summary sentence, as follows: \n",
    "\n",
    "$Recall_{lcs} = \\cfrac{LCS(X,Y)}{m}$\n",
    "\n",
    "$Precision_{lcs} = \\cfrac{LCS(X,Y)}{n}$\n",
    "\n",
    "$F_{lcs} = \\cfrac{(1+\\beta²)Recall_{lcs} Precision_{lcs}}{\\beta²Precision_{lcs}+Recall_{lcs}}$\n",
    "\n",
    "$\\beta = \\cfrac{Precision_{lcs}}{Recall_{lcs}}$\n",
    "\n",
    "$ROUGE-L = \\cfrac{(1+(\\cfrac{Precision_{lcs}}{Recall_{lcs}})²)Recall_{lcs} Precision_{lcs}}{(\\cfrac{Precision_{lcs}}{Recall_{lcs}})²Precision_{lcs}+Recall_{lcs}}$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3fddf9ef-1e46-4691-9f38-6186affdc56e",
   "metadata": {},
   "source": [
    "### LCS"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "24732e0c-2b74-428e-aeb9-99ae87f0bf09",
   "metadata": {},
   "source": [
    "Size of LCS:\n",
    "\n",
    "$ LCS(X_i, Y_j) =\n",
    "  \\begin{cases}\n",
    "    0       & \\quad \\text{if } i=0 \\text{ or } j=0 \\\\\n",
    "    LCS(X_{i-1}, Y_{j-1}) + 1  & \\quad \\text{if } i,j>0 \\text{ and } x_i=y_j \\\\\n",
    "    max\\left\\{LCS(X_i, Y_{j-1}),LCS(X_{i-1}, Y_j)\\right\\}  & \\quad \\text{if } i,j>0 \\text{ and } x_i \\neq y_j\n",
    "  \\end{cases}\n",
    "$\n",
    "\n",
    "String of LCS:\n",
    "\n",
    "$ LCS(X_i, Y_j) =\n",
    "  \\begin{cases}\n",
    "    \\epsilon       & \\quad \\text{if } i=0 \\text{ or } j=0 \\\\\n",
    "    LCS(X_{i-1}, Y_{j-1})\\frown x_i  & \\quad \\text{if } i,j>0 \\text{ and } x_i=y_j \\\\\n",
    "    max\\left\\{LCS(X_i, Y_{j-1}),LCS(X_{i-1}, Y_j)\\right\\}  & \\quad \\text{if } i,j>0 \\text{ and } x_i \\neq y_j\n",
    "  \\end{cases}\n",
    "$\n",
    "\n",
    "$\\epsilon \\implies \\text{empty string}$\n",
    "\n",
    "$\\frown \\implies \\text{append element}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "de083db6-b3d5-4ea2-b4d9-428f4b4e0330",
   "metadata": {},
   "outputs": [],
   "source": [
    "reference = \"police killed the gunman\"\n",
    "candidate = \"police kill the gunman\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "8b4f775b-3589-4bd3-9ca3-e34baf57f79b",
   "metadata": {},
   "outputs": [],
   "source": [
    "#Recursive LCS\n",
    "def lcs(X, Y, m, n):\n",
    "    if m == 0 or n == 0:\n",
    "        return 0\n",
    "    elif X[m-1] == Y[n-1]:\n",
    "        return 1 + lcs(X, Y, m-1, n-1)\n",
    "    else:\n",
    "        return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "cb1e0663-0319-42b4-b227-c6f173790525",
   "metadata": {},
   "outputs": [],
   "source": [
    "def lcs_sequence(X, Y, m, n):\n",
    "    if m == 0 or n == 0:\n",
    "        return []\n",
    "    elif X[m-1] == Y[n-1]:\n",
    "        \n",
    "        return lcs_sequence(X, Y, m-1, n-1) + [X[m-1]]\n",
    "    else:\n",
    "        a = lcs_sequence(X, Y, m, n-1)\n",
    "        b = lcs_sequence(X, Y, m-1, n)\n",
    "        return a if len(a) > len(b) else b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "da01700a-6a51-44e5-a66f-504995097526",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X = reference.split()\n",
    "Y = candidate.split()\n",
    "lcs(X, Y, len(X), len(Y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "73677fbd-8ef7-4712-a9ec-8c6e58c57a9f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'police the gunman'"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\" \".join(lcs_sequence(X, Y, len(X), len(Y)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "c1dfda73-a64f-45d2-8ebd-3f725986f34a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Dynamic Programming LCS\n",
    "def lcs_dp(X, Y, m, n, dp):\n",
    " \n",
    "    if m == 0 or n == 0:\n",
    "        return 0\n",
    "    elif dp[m][n] != -1:\n",
    "        return dp[m][n]\n",
    "    elif X[m - 1] == Y[n - 1]:\n",
    "        dp[m][n] = 1 + lcs_dp(X, Y, m - 1, n - 1, dp)\n",
    "        return dp[m][n]\n",
    " \n",
    "    dp[m][n] = max(lcs_dp(X, Y, m, n - 1, dp), lcs_dp(X, Y, m - 1, n, dp))\n",
    "    return dp[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "6cedc396-cd4c-4a48-bc74-cb88249bcba1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dp = [[-1 for i in range(len(X) + 1)] for j in range(len(Y) + 1)]\n",
    "lcs_score = lcs_dp(X, Y, len(X), len(Y), dp)\n",
    "lcs_score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "d7dc4059-1211-48e8-b51b-f4f2b2933b5f",
   "metadata": {},
   "outputs": [],
   "source": [
    "r_lcs = lcs_score/len(X)\n",
    "p_lcs = lcs_score/len(Y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "6f95adc9-4e13-4a4f-9c88-f43579d235f4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.75"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r_lcs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "4126030a-7681-43b1-9893-67b38384f47c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.75"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p_lcs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "807902ed-ceb1-42cc-8874-24ed55f3a34b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Default beta, can be another number to weight between precision and recall\n",
    "beta = p_lcs / r_lcs\n",
    "beta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "3b43959c-0860-4c04-8b08-e325752ee02e",
   "metadata": {},
   "outputs": [],
   "source": [
    "num = (1 + (beta**2)) * r_lcs * p_lcs\n",
    "denom = r_lcs + ((beta**2) * p_lcs)\n",
    "rouge_l = num / denom"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "34ea1e90-477c-428f-b87a-3cc0e3f0eb84",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.75"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rouge_l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "7536b6dc-8ede-4db1-a75f-b01a62d5dcbe",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rouge_l(reference, candidate):\n",
    "    X = reference.split()\n",
    "    Y = candidate.split()\n",
    "    m = len(X)\n",
    "    n = len(Y)\n",
    "    if m == 0 or n == 0:\n",
    "        return 0\n",
    "    \n",
    "    dp = [[-1 for i in range(n + 1)]for j in range(m + 1)]\n",
    "    lcs_score = lcs_dp(X, Y, m, n, dp)\n",
    "    r_lcs = lcs_score/m\n",
    "    p_lcs = lcs_score/n\n",
    "    \n",
    "    epsilon = 1e-12 # Prevents division by 0\n",
    "    r_lcs = epsilon if r_lcs == 0 else r_lcs\n",
    "    beta = p_lcs / (r_lcs + epsilon)\n",
    "    num = (1 + (beta**2)) * r_lcs * p_lcs\n",
    "    denom = r_lcs + ((beta**2) * p_lcs)\n",
    "    denom = epsilon if denom == 0 else denom\n",
    "    return num / denom"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "60ff77c7-1064-4278-9b86-fdac98572715",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.75"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rouge_l(reference, candidate)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0e2b4796-beef-4632-9f9a-7df054e26e56",
   "metadata": {},
   "source": [
    "## Google Research Implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "8db2aeae-db9c-446d-ab7d-dbd08f040235",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Requirement already satisfied: rouge-score in ./venv/lib/python3.9/site-packages (0.1.2)\n",
      "Requirement already satisfied: absl-py in ./venv/lib/python3.9/site-packages (from rouge-score) (1.4.0)\n",
      "Requirement already satisfied: nltk in ./venv/lib/python3.9/site-packages (from rouge-score) (3.8.1)\n",
      "Requirement already satisfied: numpy in ./venv/lib/python3.9/site-packages (from rouge-score) (1.25.2)\n",
      "Requirement already satisfied: six>=1.14.0 in ./venv/lib/python3.9/site-packages (from rouge-score) (1.16.0)\n",
      "Requirement already satisfied: regex>=2021.8.3 in ./venv/lib/python3.9/site-packages (from nltk->rouge-score) (2023.8.8)\n",
      "Requirement already satisfied: tqdm in ./venv/lib/python3.9/site-packages (from nltk->rouge-score) (4.66.1)\n",
      "Requirement already satisfied: joblib in ./venv/lib/python3.9/site-packages (from nltk->rouge-score) (1.3.2)\n",
      "Requirement already satisfied: click in ./venv/lib/python3.9/site-packages (from nltk->rouge-score) (8.1.7)\n"
     ]
    }
   ],
   "source": [
    "!pip install rouge-score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "03a1609c-4448-4b3e-a79d-c60bc7a9c076",
   "metadata": {},
   "outputs": [],
   "source": [
    "from rouge_score import rouge_scorer\n",
    "\n",
    "scorer = rouge_scorer.RougeScorer(['rougeL'], use_stemmer=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "ba8d85aa-3bf5-4f17-9ccc-8b23fc569c56",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'rougeL': Score(precision=0.75, recall=0.75, fmeasure=0.75)}"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "scorer.score(reference, candidate)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "c2033ca1-f9ea-45b5-b77f-2a5313ffb7d4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'rougeL': Score(precision=0.625, recall=0.5555555555555556, fmeasure=0.5882352941176471)}"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "scorer.score('The quick brown fox jumps over the lazy dog',\n",
    "                      'The quick brown dog jumps on the log.')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
